﻿#include "BinarySearchTree.h"
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>

using namespace std;

BinarySearchTree::BinarySearchTree()
{
	root = nullptr;
}

static void morrisOrder(BinaryTreeNode* head)
{
	auto cur = head;
	while (cur)
	{
		if (!cur->left)
		{
			cur = cur->right;
			continue;
		}

		auto mostRight = cur->left;
		while (mostRight->right && mostRight->right != cur)
		{
			mostRight = mostRight->right;
		}

		if (!mostRight->right)
		{
			mostRight->right = cur;
			cur = cur->left;
		}
		else
		{
			mostRight->right = nullptr;
			cur = cur->right;
		}
	}
}

static BinaryTreeNode* reverseRight(BinaryTreeNode* node)
{
	auto cur = node;
	BinaryTreeNode* next = nullptr;
	BinaryTreeNode* prev = nullptr;
	if (!cur->right) return cur;

	while (cur->right)
	{
		next = cur->right;
		cur->right = prev;
		prev = cur;
		cur = next;
	}

	cur->right = prev;
	return cur;
}

static void morrisPostOrder(BinaryTreeNode* head)
{
	auto cur = head;
	BinaryTreeNode* reversedHead = nullptr;
	BinaryTreeNode* node = nullptr;
	while (cur)
	{
		if (!cur->left)
		{
			cur = cur->right;
			continue;
		}

		auto mostRight = cur->left;
		while (mostRight->right && mostRight->right != cur)
		{
			mostRight = mostRight->right;
		}

		if (!mostRight->right)
		{
			mostRight->right = cur;
			cur = cur->left;
		}
		else
		{
			mostRight->right = nullptr;

			reversedHead = reverseRight(cur->left);
			node = reversedHead;
			while (node)
			{
				printf("%d->", node->value);
				node = node->right;
			}

			reverseRight(reversedHead);

			cur = cur->right;
		}
	}

	reversedHead = reverseRight(head);
	node = reversedHead;
	while (node)
	{
		printf("%d->", node->value);
		node = node->right;
	}

	reverseRight(reversedHead);

	printf("\n");
}

BinarySearchTree::~BinarySearchTree()
{
	// 后序遍历删除所有节点
	vector<BinaryTreeNode*> nodes;
	auto cur = root;
	BinaryTreeNode* reversedHead = nullptr;
	BinaryTreeNode* node = nullptr;
	while (cur)
	{
		if (!cur->left)
		{
			cur = cur->right;
			continue;
		}

		auto mostRight = cur->left;
		while (mostRight->right && mostRight->right != cur)
		{
			mostRight = mostRight->right;
		}

		if (!mostRight->right)
		{
			mostRight->right = cur;
			cur = cur->left;
		}
		else
		{
			mostRight->right = nullptr;

			reversedHead = reverseRight(cur->left);
			node = reversedHead;
			while (node)
			{
				nodes.push_back(node);
				node = node->right;
			}

			reverseRight(reversedHead);

			cur = cur->right;
		}
	}

	reversedHead = reverseRight(root);
	node = reversedHead;
	while (node)
	{
		nodes.push_back(node);
		node = node->right;
	}

	reverseRight(reversedHead);

	for (auto itor = nodes.begin(); itor != nodes.end(); ++itor)
	{
		delete(*itor);
	}
}

BinaryTreeNode* BinarySearchTree::find(int value)
{
	if (!root) return nullptr;
	if (root->value == value) return root;
	
	auto cur = root;
	while (true)
	{
		if (!cur) return nullptr;

		if (cur->value == value) return cur;

		if (value < cur->value)
		{
			cur = cur->left;
			continue;
		}

		if (value > cur->value)
		{
			cur = cur->right;
			continue;
		}
	}
}

BinaryTreeNode* BinarySearchTree::add(int value)
{
	if (!root)
	{
		root = new BinaryTreeNode(value);
		return root;
	}

	auto exists = find(value);
	if (exists) return exists;

	auto cur = root;
	while (true)
	{
		if (value < cur->value)
		{
			if (!cur->left)
			{
				cur->left = new BinaryTreeNode(value);
				cur->left->parent = cur;
				return cur->left;
			}

			cur = cur->left;
		}
		else if (value > cur->value)
		{
			if (!cur->right)
			{
				cur->right = new BinaryTreeNode(value);
				cur->right->parent = cur;
				return cur->right;
			}

			cur = cur->right;
		}
	}
}

void BinarySearchTree::remove(int value)
{
	auto node = find(value);
	if (!node) return;

	auto parent = node->parent;
	if (!node->left && !node->right)
	{
		if (parent)
		{
			if (parent->left == node)
			{
				parent->left = nullptr;
			}
			else
			{
				parent->right = nullptr;
			}
		}
		else
		{
			// 没有父节点肯定就是root
			root = nullptr;
		}
	}
	else if (!node->left)
	{
		node->right->parent = parent;
		if (parent)
		{
			if (parent->left == node)
			{
				parent->left = node->right;
			}
			else
			{
				parent->right = node->right;
			}
		}
		else
		{
			root = node->right;
		}
	}
	else if (!node->right)
	{
		node->left->parent = parent;
		if (parent)
		{
			if (parent->left == node)
			{
				parent->left = node->left;
			}
			else
			{
				parent->right = node->left;
			}
		}
		else
		{
			root = node->left;
		}
	}
	else
	{
		// 左右节点都有，则需要把左子树的最右节点，或者右子树的最左节点提上来代替原node的位置
		// 这里选节点数多的那一边提上来。
		size_t leftSize = node->left->getNodeCount();
		size_t rightSize = node->right->getNodeCount();
		if (leftSize >= rightSize)
		{
			auto mostRight = node->left;
			while (mostRight->right)
			{
				mostRight = mostRight->right;
			}

			auto originalMostRightParent = mostRight->parent;
			mostRight->parent = parent;
			if (parent)
			{
				if (parent->left == node)
				{
					parent->left = mostRight;
				}
				else
				{
					parent->right = mostRight;
				}
			}
			else
			{
				root = mostRight;
			}

			if (mostRight->left)
			{
				mostRight->left->parent = originalMostRightParent;
			}

			if (originalMostRightParent != node)
			{
				originalMostRightParent->right = mostRight->left;
			}

			if (node->left != mostRight)
			{
				mostRight->left = node->left;
				node->left->parent = mostRight;
			}

			mostRight->right = node->right;

			if (node->right)
			{
				node->right->parent = mostRight;
			}
		}
		else
		{
			auto mostLeft = node->right;
			while (mostLeft->left)
			{
				mostLeft = mostLeft->left;
			}

			auto originalMostLeftParent = mostLeft->parent;
			mostLeft->parent = parent;
			if (parent)
			{
				if (parent->left == node)
				{
					parent->left = mostLeft;
				}
				else
				{
					parent->right = mostLeft;
				}
			}
			else
			{
				root = mostLeft;
			}

			if (mostLeft->right)
			{
				mostLeft->right->parent = originalMostLeftParent;
			}

			if (originalMostLeftParent != node)
			{
				originalMostLeftParent->left = mostLeft->right;
			}

			mostLeft->left = node->left;
			if (node->right != mostLeft)
			{
				mostLeft->right = node->right;
				node->right->parent = mostLeft;
			}

			if (node->left)
			{
				node->left->parent = mostLeft;
			}
		}
	}

	delete(node);
}

BinaryTreeNode* BinarySearchTree::leftRotate(BinaryTreeNode* head)
{
	if (!head) return nullptr;

	auto originalParent = head->parent;
	bool isHeadLeftChild = false;
	bool isHeadRightChild = false;
	if (originalParent)
	{
		isHeadLeftChild = originalParent->left == head;
		isHeadRightChild = originalParent->right == head;
	}

	auto originalRight = head->right;
	if (!originalRight) return nullptr;

	head->right = originalRight->left;
	if (originalRight->left)
	{
		originalRight->left->parent = head;
	}

	originalRight->left = head;
	head->parent = originalRight;
	originalRight->parent = originalParent;
	if (!originalParent)
	{
		root = originalRight;
	}
	else if (isHeadLeftChild)
	{
		originalParent->left = originalRight;
	}
	else
	{
		originalParent->right = originalRight;
	}

	return originalRight;
}

BinaryTreeNode* BinarySearchTree::rightRotate(BinaryTreeNode* head)
{
	if (!head) return nullptr;

	auto originalParent = head->parent;
	bool isHeadLeftChild = false;
	bool isHeadRightChild = false;
	if (originalParent)
	{
		isHeadLeftChild = originalParent->left == head;
		isHeadRightChild = originalParent->right == head;
	}

	auto originalLeft = head->left;
	if (!originalLeft) return nullptr;

	head->left = originalLeft->right;
	if (originalLeft->right)
	{
		originalLeft->right->parent = head;
	}

	originalLeft->right = head;
	head->parent = originalLeft;
	originalLeft->parent = originalParent;
	if (!originalParent)
	{
		root = originalLeft;
	}
	else if (isHeadLeftChild)
	{
		originalParent->left = originalLeft;
	}
	else
	{
		originalParent->right = originalLeft;
	}

	return originalLeft;
}

int main_BinarySearchTree()
{
	auto tree = new BinarySearchTree();
	tree->add(20);
	tree->add(10);
	tree->add(5);
	tree->add(15);
	tree->add(3);
	tree->add(7);
	tree->add(1);
	tree->add(2);
	tree->add(6);
	tree->add(9);
	tree->add(13);
	tree->add(11);
	tree->add(14);
	tree->add(17);
	tree->add(16);
	tree->add(18);
	tree->add(30);
	tree->add(25);
	tree->add(36);
	tree->add(22);
	tree->add(26);
	tree->add(33);
	tree->add(32);
	tree->add(34);
	tree->add(40);
	tree->add(37);
	tree->add(41);

	tree->rightRotate(tree->find(20));
	delete(tree);
	return 0;
}